{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Array By Parity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortArrayByParity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按奇偶排序数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>，将 <code>nums</code> 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。</p>\n",
    "\n",
    "<p>返回满足此条件的 <strong>任一数组</strong> 作为答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1,2,4]\n",
    "<strong>输出：</strong>[2,4,3,1]\n",
    "<strong>解释：</strong>[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 5000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-array-by-parity](https://leetcode.cn/problems/sort-array-by-parity/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-array-by-parity](https://leetcode.cn/problems/sort-array-by-parity/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,2,4]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def sortArrayByParityII(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        if not A:\n",
    "          return []\n",
    "\n",
    "        even,odd=0,1\n",
    "\n",
    "        while even<len(A) and odd<len(A):\n",
    "          if A[even]%2==0:\n",
    "            even+=2\n",
    "          else:\n",
    "            A[even],A[odd]=A[odd],A[even]\n",
    "            odd+=2\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 时间复杂度：O(N)，其中 N 是数组 nums 的长度。\n",
    "# 空间复杂度：O(1)。\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        oddIndex = 1\n",
    "\n",
    "        # 步长为2\n",
    "        for i in range(0, len(nums), 2): \n",
    "            # 偶数位遇到奇数\n",
    "            if nums[i] % 2: \n",
    "                # 奇数位找偶数\n",
    "                while nums[oddIndex] % 2: \n",
    "                    oddIndex += 2\n",
    "                nums[i], nums[oddIndex] = nums[oddIndex], nums[i]\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        even, odd = 0, 1\n",
    "\n",
    "        while even < len(nums) and odd < len(nums):\n",
    "            while even < len(nums) and nums[even] % 2 == 0:\n",
    "                even += 2\n",
    "            while odd < len(nums) and nums[odd] % 2 == 1:\n",
    "                odd += 2\n",
    "            if odd < len(nums):\n",
    "                nums[even], nums[odd] = nums[odd], nums[even]\n",
    "        \n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        oddIndex = 1\n",
    "        for i in range(0 , len(nums) , 2):\n",
    "            if nums[i] % 2 ==1:\n",
    "                while nums[oddIndex] % 2 != 0:\n",
    "                    oddIndex += 2\n",
    "                nums[i] , nums[oddIndex] = nums[oddIndex] , nums[i]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        left ,right = 0, 1\n",
    "        while left < len(nums) and right < len(nums):\n",
    "            if nums[left] % 2 != 0:\n",
    "                if nums[right]%2==0:\n",
    "                    nums[left], nums[right] = nums[right], nums[left]\n",
    "                else:\n",
    "                    right += 2\n",
    "            else:\n",
    "                left += 2\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        st, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 0:\n",
    "                tmp = nums[st]\n",
    "                nums[st] = nums[i]\n",
    "                nums[i] = tmp\n",
    "                st += 1\n",
    "        # return nums\n",
    "        st1 = (st + 1) // 2 * 2\n",
    "        for i in range(1, st, 2):\n",
    "            tmp = nums[i]\n",
    "            nums[i] = nums[st1]\n",
    "            nums[st1] = tmp\n",
    "            st1 += 2\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        # ar = [0] * len(nums)\n",
    "        # even, odd = 0, 1\n",
    "        # for n in nums:\n",
    "        #     if n % 2 == 0:\n",
    "        #         ar[even] = n\n",
    "        #         even += 2\n",
    "        #     else:\n",
    "        #         ar[odd] = n\n",
    "        #         odd += 2\n",
    "        # return ar\n",
    "\n",
    "        even, odd = 0, 1\n",
    "        while even < len(nums) and odd < len(nums):\n",
    "            ne, no = nums[even] % 2, nums[odd] % 2\n",
    "            if ne != 0 and no == 0:\n",
    "                nums[even], nums[odd] = nums[odd], nums[even]\n",
    "                even += 2\n",
    "                odd += 2\n",
    "            else:\n",
    "                if ne == 0:\n",
    "                    even += 2\n",
    "                if no != 0:\n",
    "                    odd += 2\n",
    "        return nums\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        oddIdx = 1\n",
    "        for i in range(0, len(nums), 2):\n",
    "            if nums[i] % 2 == 1:  # 偶数位遇到奇数, 需要找一个奇数位为偶数\n",
    "                while nums[oddIdx] % 2 != 0:\n",
    "                    oddIdx += 2\n",
    "                nums[i], nums[oddIdx] = nums[oddIdx], nums[i]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        even, odd = 0, 1\n",
    "        for i in range(len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                while nums[even] % 2:\n",
    "                    even += 1\n",
    "                nums[i], nums[even] = nums[even], nums[i]\n",
    "                even += 1\n",
    "            else:\n",
    "                while nums[odd] % 2 == 0:\n",
    "                    odd += 1\n",
    "                nums[i], nums[odd] = nums[odd], nums[i]\n",
    "                odd += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        odd = 1\n",
    "        even = 0\n",
    "\n",
    "        while odd < n and even < n:\n",
    "            if nums[n - 1] & 1 == 1:\n",
    "                self.swap(nums, odd, n - 1)\n",
    "                odd += 2\n",
    "            else:\n",
    "                self.swap(nums, even, n - 1)\n",
    "                even += 2\n",
    "\n",
    "        return nums\n",
    "\n",
    "    def swap(self, nums: List[int], i: int, j: int) -> None:\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        index, temp, n = 0, 1, len(nums)\n",
    "        while temp < n :\n",
    "            while index < n and nums[index]%2 == 0:\n",
    "                index += 2\n",
    "            while temp < n and nums[temp]%2 != 0:\n",
    "                temp += 2\n",
    "            if temp < n :\n",
    "                nums[index], nums[temp] = nums[temp], nums[index]\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\r\n",
    "        i,j,n = 0,1,len(nums)\r\n",
    "        while True:\r\n",
    "            while i < n and nums[i]%2 == 0:\r\n",
    "                i += 2\r\n",
    "            while j < n and nums[j]%2 == 1:\r\n",
    "                j += 2\r\n",
    "            if i < n and j < n:\r\n",
    "                tmp = nums[i]\r\n",
    "                nums[i] = nums[j]\r\n",
    "                nums[j] = tmp \r\n",
    "            else:\r\n",
    "                break\r\n",
    "        return nums\r\n",
    "            \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ji_p = 1\n",
    "        ou_p = 0\n",
    "        n = len(nums)\n",
    "        while ji_p<n and ou_p<n:\n",
    "            while nums[ji_p]%2==1:\n",
    "                ji_p += 2\n",
    "                if ji_p>n-1:\n",
    "                    return nums\n",
    "            while nums[ou_p]%2==0:\n",
    "                ou_p += 2\n",
    "                if ou_p>n-1:\n",
    "                    return nums\n",
    "            \n",
    "            # 交换\n",
    "            tmp = nums[ji_p]\n",
    "            nums[ji_p] = nums[ou_p]\n",
    "            nums[ou_p] = tmp\n",
    "            ji_p += 2\n",
    "            ou_p += 2\n",
    "\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        odd = 1\n",
    "        even = 0\n",
    "\n",
    "        while odd < n and even < n:\n",
    "            if nums[n - 1] & 1 == 1:\n",
    "                self.swap(nums, odd, n - 1)\n",
    "                odd += 2\n",
    "            else:\n",
    "                self.swap(nums, even, n - 1)\n",
    "                even += 2\n",
    "\n",
    "        return nums\n",
    "\n",
    "    def swap(self, nums: List[int], i: int, j: int) -> None:\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        peven=0\n",
    "        podd=1\n",
    "        while peven<len(nums) and podd<len(nums):\n",
    "            if nums[peven]%2!=0 and nums[podd]%2!=1:\n",
    "                nums[peven],nums[podd]=nums[podd],nums[peven]\n",
    "                peven+=2\n",
    "                podd+=2\n",
    "            elif nums[peven]%2!=0:\n",
    "                podd+=2\n",
    "            else:\n",
    "                peven+=2\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        # ar = [0] * len(nums)\n",
    "        # even, odd = 0, 1\n",
    "        # for n in nums:\n",
    "        #     if n % 2 == 0:\n",
    "        #         ar[even] = n\n",
    "        #         even += 2\n",
    "        #     else:\n",
    "        #         ar[odd] = n\n",
    "        #         odd += 2\n",
    "        # return ar\n",
    "\n",
    "        even, odd = 0, 1\n",
    "        while even < len(nums) and odd < len(nums):\n",
    "            if nums[even] % 2 != 0 and nums[odd] % 2 == 0:\n",
    "                nums[even], nums[odd] = nums[odd], nums[even]\n",
    "                even += 2\n",
    "                odd += 2\n",
    "            else:\n",
    "                if nums[even] % 2 == 0:\n",
    "                    even += 2\n",
    "                if nums[odd] % 2 != 0:\n",
    "                    odd += 2\n",
    "        return nums\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        oddIndex = 1\n",
    "        for i in range(0, len(nums), 2):\n",
    "            if nums[i] % 2:\n",
    "                while nums[oddIndex] % 2:\n",
    "                    oddIndex += 2\n",
    "                nums[i], nums[oddIndex] = nums[oddIndex], nums[i]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "         for i in range(len(nums)):\n",
    "             if (i%2 == 0 and nums[i]%2!=0)or(i%2 != 0 and nums[i]%2 ==0):\n",
    "                 if i%2 == 0:\n",
    "                     for j in range(i, len(nums)+1):\n",
    "                        if nums[j] % 2 == 0:\n",
    "                            nums[i], nums[j] = nums[j], nums[i]\n",
    "                            break\n",
    "                 else:\n",
    "                    for j in range(i,len(nums)+1):\n",
    "                         if nums[j] % 2 !=0:\n",
    "                             nums[i],nums[j]=nums[j],nums[i]\n",
    "                             break\n",
    "             else:\n",
    "                 continue\n",
    "         return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst_even = []\n",
    "        for i in range(len(nums) - 1,-1,-1):\n",
    "            if not nums[i] % 2:\n",
    "                lst_even.append(nums.pop(i))\n",
    "        for i in range(len(lst_even)):\n",
    "            nums.insert(i * 2,lst_even[i])\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst_even = []\n",
    "        for i in range(len(nums) - 1,-1,-1):\n",
    "            if not nums[i] % 2:\n",
    "                lst_even.append(nums.pop(i))\n",
    "        for i in range(len(lst_even)):\n",
    "            nums.insert(i * 2,lst_even[i])\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst_even = []\n",
    "        for i in range(len(nums) - 1,-1,-1):\n",
    "            if not nums[i] % 2:\n",
    "                lst_even.append(nums.pop(i))\n",
    "        for i in range(len(lst_even)):\n",
    "            nums.insert(i * 2,lst_even[i])\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(key=lambda x:x%2)\n",
    "        s=len(nums)//2\n",
    "        for i in range(1,s,2):\n",
    "            nums[i],nums[s*2-i-1]=nums[s*2-i-1],nums[i]\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        point1 = 0\n",
    "        point2 = 1\n",
    "        while point1 < len(nums) and point2 < len(nums):\n",
    "            while point1 < len(nums) and nums[point1] % 2 == 0:\n",
    "                point1 += 2\n",
    "            while point2 < len(nums) and nums[point2] % 2 == 1:\n",
    "                point2 += 2\n",
    "            if point1 < len(nums) and point2 < len(nums):\n",
    "                nums[point1], nums[point2] = nums[point2], nums[point1]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left < len(nums) and right > 0:\n",
    "            if nums[left] % 2 != 0 and nums[right] % 2 != 1:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "            elif nums[left] % 2 != 0:\n",
    "                right -= 2\n",
    "            else:\n",
    "                left += 2\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        oddIndx = 1\n",
    "        for i in range(0, len(nums), 2):\n",
    "            if nums[i] % 2:\n",
    "                while nums[oddIndx] % 2:\n",
    "                    oddIndx += 2\n",
    "                nums[i], nums[oddIndx] = nums[oddIndx], nums[i]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        even_ptr,odd_ptr = 0,1\n",
    "        while even_ptr<n and odd_ptr<n:\n",
    "            while even_ptr<n and nums[even_ptr]%2==0:\n",
    "                even_ptr+=2\n",
    "            while odd_ptr<n and nums[odd_ptr]%2==1:\n",
    "                odd_ptr+=2\n",
    "            \n",
    "            if odd_ptr<n and even_ptr<n:\n",
    "                nums[odd_ptr],nums[even_ptr]=nums[even_ptr],nums[odd_ptr]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        i,j = 0,1\n",
    "        n = len(nums)\n",
    "        while i<n:\n",
    "            while i<n and nums[i]%2==0:\n",
    "                i+=2\n",
    "            while j<n and nums[j]%2==1:\n",
    "                j+=2\n",
    "            if i<n:\n",
    "                nums[i],nums[j]=nums[j],nums[i]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        def sortArrayByParityII_array(nums):\n",
    "            odd = []\n",
    "            even = []\n",
    "            for i in nums:\n",
    "                if i % 2 == 0:\n",
    "                    even.append(i)\n",
    "                else:\n",
    "                    odd.append(i)\n",
    "            for idx, i in enumerate(even):\n",
    "                nums[idx * 2] = i\n",
    "            for idx, i in enumerate(odd):\n",
    "                nums[idx * 2 + 1] = i\n",
    "            return nums\n",
    "        def sortArrayByParityII_twopointer(nums):\n",
    "            even = 0\n",
    "            odd = 1\n",
    "            cur = len(nums) - 1\n",
    "            while even < len(nums) and odd < len(nums):\n",
    "                if nums[cur] % 2 == 0:\n",
    "                    nums[even], nums[cur] = nums[cur], nums[even]\n",
    "                    even += 2\n",
    "                else:\n",
    "                    nums[odd], nums[cur] = nums[cur], nums[odd]\n",
    "                    odd += 2\n",
    "            return nums\n",
    "        return sortArrayByParityII_twopointer(nums)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        slow, fast = 0, 1\n",
    "        while fast < len(nums):\n",
    "            while slow < len(nums) and nums[slow] % 2 == 0:\n",
    "                slow += 2\n",
    "            while fast < len(nums) and nums[fast] % 2 == 1:\n",
    "                fast += 2\n",
    "            if slow > len(nums) - 1 or fast > len(nums) - 1:\n",
    "                break\n",
    "            nums[slow], nums[fast] = nums[fast], nums[slow]\n",
    "            slow += 2\n",
    "            fast += 2\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        j, k = 0, 1\n",
    "        res = len(nums)*[0]\n",
    "        while j < len(nums):\n",
    "            for i in range(0,len(nums)): #0,2\n",
    "                if nums[i] % 2 == 0:\n",
    "                    res[j] = nums[i]\n",
    "                    nums[i] = 0\n",
    "                    j += 2\n",
    "                else:\n",
    "                    res[k] = nums[i]\n",
    "                    k += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst1 = [item for item in nums if item % 2 == 1]\n",
    "        lst2 = [item for item in nums if item % 2 == 0]\n",
    "        nums[::2] = lst2\n",
    "        nums[1::2] = lst1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ji=[]\n",
    "        ou=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                ou.extend([i])\n",
    "            else:\n",
    "                ji.extend([i])\n",
    "        nums[::2]=ou\n",
    "        nums[1::2]=ji\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        n=[]\n",
    "        m=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                n.append(i)\n",
    "            else:\n",
    "                m.append(i)\n",
    "        nums[::2]=n\n",
    "        nums[1::2]=m\n",
    "        return nums\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        def sortArrayByParityII_array(nums):\n",
    "            odd = []\n",
    "            even = []\n",
    "            for i in nums:\n",
    "                if i % 2 == 0:\n",
    "                    even.append(i)\n",
    "                else:\n",
    "                    odd.append(i)\n",
    "            for idx, i in enumerate(even):\n",
    "                nums[idx * 2] = i\n",
    "            for idx, i in enumerate(odd):\n",
    "                nums[idx * 2 + 1] = i\n",
    "            return nums\n",
    "        def sortArrayByParityII_twopointer(nums):\n",
    "            even = 0\n",
    "            odd = 1\n",
    "            i = 0\n",
    "            while i < len(nums):\n",
    "                if nums[i] % 2 == 0 and i % 2 != 0:\n",
    "                    nums[i], nums[even] = nums[even], nums[i]\n",
    "                    even += 2\n",
    "                elif nums[i] % 2 != 0 and i % 2 == 0:\n",
    "                    nums[i], nums[odd] = nums[odd], nums[i]\n",
    "                    odd += 2\n",
    "                else:\n",
    "                    i += 1\n",
    "            return nums\n",
    "        return sortArrayByParityII_twopointer(nums)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        length = len(nums)\n",
    "        nums.sort(key=lambda x:x%2)\n",
    "        new_nums = [0]*length\n",
    "        new_nums[::2]=nums[:length//2]\n",
    "        new_nums[1::2]=nums[length//2:]\n",
    "        return new_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        cur_e=0\n",
    "        cur_o=1\n",
    "        result=[0]*len(nums)\n",
    "        for n in nums:\n",
    "            if n%2==0:\n",
    "                result[cur_e]=n\n",
    "                cur_e+=2\n",
    "            else:\n",
    "                result[cur_o]=n\n",
    "                cur_o+=2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst = [0]*len(nums)\n",
    "        t = 0\n",
    "        s = 1\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lst[t]=i\n",
    "                t += 2\n",
    "            else:\n",
    "                lst[s]=i\n",
    "                s += 2\n",
    "        return lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        a=[x for x in nums if x%2==0]\n",
    "        b=[x for x in nums if x%2!=0]\n",
    "        if a[0]%2==0:\n",
    "            nums[::2]=a\n",
    "            nums[1::2]=b\n",
    "        else:\n",
    "            nums[::2]=b\n",
    "            nums[1::2]=a\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        length = len(nums)\n",
    "        nums.sort(key=lambda x:x%2)\n",
    "        new_nums = [0]*length\n",
    "        new_nums[::2]=nums[:length//2]\n",
    "        new_nums[1::2]=nums[length//2:]\n",
    "        return new_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        l,r = 0,1\n",
    "        for i in range(n):\n",
    "            if nums[i]%2:\n",
    "                ans[r] = nums[i]\n",
    "                r += 2\n",
    "            else:\n",
    "                ans[l] = nums[i]\n",
    "                l += 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "            lstj = []\n",
    "            lsto = []\n",
    "            for i in nums:\n",
    "                if i % 2 == 0:\n",
    "                    lsto.append(i)\n",
    "                else:\n",
    "                    lstj.append(i)\n",
    "            nums[::2] = lsto\n",
    "            nums[1::2] = lstj\n",
    "            return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        odd, even = 1, 0\n",
    "        for i in nums:\n",
    "            if i % 2 == 0:\n",
    "                ans[even] = i\n",
    "                even += 2\n",
    "            else:\n",
    "                ans[odd] = i\n",
    "                odd += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        a = sorted(nums, key = lambda x:x%2)\n",
    "        nums[::2] = a[:len(nums)//2]\n",
    "        nums[1::2] = a[len(nums)//2:]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ans=[0]*len(nums)\n",
    "        i=0\n",
    "        j=1\n",
    "        for num in nums:\n",
    "            if num%2==0:\n",
    "                ans[i]=num\n",
    "                i+=2\n",
    "            if num%2!=0:\n",
    "                ans[j]=num\n",
    "                j+=2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        even = 0\n",
    "        odd = 1\n",
    "        res = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%2==0:\n",
    "                res[even]=nums[i]\n",
    "                even+=2\n",
    "            else:\n",
    "                res[odd]=nums[i]\n",
    "                odd+=2\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        o=filter(lambda x:x%2==1,nums)\n",
    "        e=filter(lambda x:x%2==0,nums)\n",
    "        ans=[]\n",
    "        for i,j in zip(e,o):\n",
    "            ans.append(i)\n",
    "            ans.append(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst_1=[]\n",
    "        lst_2=[]\n",
    "        for i in nums:\n",
    "            if i%2 == 0:\n",
    "                lst_1.append(i)\n",
    "            elif i%2 != 0:\n",
    "                lst_2.append(i)\n",
    "        nums[::2] = lst_1\n",
    "        nums[1::2] = lst_2\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        i = 0\n",
    "        j = 1\n",
    "        ans = []\n",
    "        for k in nums:\n",
    "            if k % 2 == 0:\n",
    "                ans.insert(i, k)\n",
    "                i += 2\n",
    "            else:\n",
    "                ans.insert(j, k)\n",
    "                j += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ans=[0]*len(nums)\n",
    "        l=0\n",
    "        r=1\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                ans[l]=i\n",
    "                l+=2\n",
    "            else:\n",
    "                ans[r]=i\n",
    "                r+=2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        odd = []\n",
    "        even = []\n",
    "        for i in nums:\n",
    "            if i % 2 == 0:\n",
    "                even.append(i)\n",
    "            else:\n",
    "                odd.append(i)\n",
    "        for idx, i in enumerate(even):\n",
    "            nums[idx * 2] = i\n",
    "        for idx, i in enumerate(odd):\n",
    "            nums[idx * 2 + 1] = i\n",
    "        return nums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(key=lambda x:x%2)\n",
    "        nums_ = [0]*len(nums)\n",
    "        nums_[::2] = nums[:len(nums)//2]\n",
    "        nums_[1::2] = nums[len(nums)//2:]\n",
    "        return nums_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:   \n",
    "        if not nums: return nums\n",
    "\n",
    "        res = list()\n",
    "        left = right = 0\n",
    "        for x in range(len(nums) // 2):\n",
    "           while (nums[left] % 2 != 0): left += 1\n",
    "           res.append(nums[left])\n",
    "           left += 1\n",
    "           while (nums[right] % 2 == 0): right += 1\n",
    "           res.append(nums[right])\n",
    "           right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        l0 = [i for i in nums if i%2==0]\n",
    "        l1 = [i for i in nums if i%2!=0]\n",
    "        res = []\n",
    "        while l0 or l1:\n",
    "            if l0:\n",
    "                res.append(l0.pop(0))\n",
    "            if l1:\n",
    "                res.append(l1.pop(0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        result = []\n",
    "        for i in nums:\n",
    "            if i%2 == 0:\n",
    "                arr1.append(i)\n",
    "            else:\n",
    "                arr2.append(i)\n",
    "        for j in range(len(arr1)):\n",
    "            result.extend([arr1[j],arr2[j]])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "        l = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 0:\n",
    "                l1.append(nums[i])\n",
    "            else:\n",
    "                l2.append(nums[i])\n",
    "        for i in range(len(l1)):\n",
    "            l.append(l1[i])\n",
    "            l.append(l2[i])\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        result = []\n",
    "        for i in nums:\n",
    "            if i%2 == 0:\n",
    "                arr1.append(i)\n",
    "            else:\n",
    "                arr2.append(i)\n",
    "\n",
    "        for j in range(len(arr1)):\n",
    "            result.extend([arr1[j],arr2[j]])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        单 = 1\n",
    "        双 = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 0:\n",
    "                res[双] = nums[i]\n",
    "                双 += 2 \n",
    "            else:\n",
    "                res[单] = nums[i]\n",
    "                单 += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        result = []\n",
    "        for i in nums:\n",
    "            if i%2 == 0:\n",
    "                arr1.append(i)\n",
    "            else:\n",
    "                arr2.append(i)\n",
    "\n",
    "        for j in range(len(arr1)):\n",
    "            result.extend([arr1[j],arr2[j]])\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst=[]\n",
    "        lst1=[]\n",
    "        lst2=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lst2.append(i)\n",
    "            else:\n",
    "                lst1.append(i)\n",
    "        for j in range(len(lst1)):\n",
    "            lst.append(lst2[j])\n",
    "            lst.append(lst1[j])\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        nums1=[]\n",
    "        nums2=[]\n",
    "        nums3=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                nums1.append(i)\n",
    "            else:\n",
    "                nums2.append(i)\n",
    "        i=len(nums)//2-1\n",
    "        while i>=0:\n",
    "            nums3.append(nums1[i])\n",
    "            nums3.append(nums2[i])\n",
    "            i-=1\n",
    "        return nums3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        l0 = [i for i in nums if i%2==0]\n",
    "        l1 = [i for i in nums if i%2!=0]\n",
    "        res = []\n",
    "        for i in range(len(l0)):\n",
    "            res.extend([l0[i],l1[i]])\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        result = []\n",
    "        for i in nums:\n",
    "            if i%2 == 0:\n",
    "                arr1.append(i)\n",
    "            else:\n",
    "                arr2.append(i)\n",
    "\n",
    "        for j in range(len(arr1)):\n",
    "            result.extend([arr1[j],arr2[j]])\n",
    "        return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        m,n=[],[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                m.insert(0,i)\n",
    "            else:\n",
    "                m.append(i)\n",
    "        i,j=0,len(nums)-1\n",
    "        while i < j:\n",
    "            n.append(m[i])\n",
    "            n.append(m[j])\n",
    "            i,j=i+1,j-1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lstji=[]\n",
    "        lstou=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lstou.append(i)\n",
    "            else:\n",
    "                lstji.append(i)\n",
    "        for i in range(len(lstji)):\n",
    "            lstou.insert(i*2+1,lstji[i])\n",
    "        return lstou"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        eve, odd = [], []\n",
    "        for num in nums:\n",
    "            if num % 2:\n",
    "                odd.append(num)\n",
    "            else:\n",
    "                eve.append(num)\n",
    "        res = []\n",
    "        for ev, ov in zip(eve, odd):\n",
    "            res.append(ev)\n",
    "            res.append(ov)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        setNums = set(nums)\n",
    "        odd = []\n",
    "        even = []\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            if i % 2 == 0:\n",
    "                even.append(i)\n",
    "            else:\n",
    "                odd.append(i)\n",
    "        for i in range(len(odd)):\n",
    "            # ans.append(even[i])\n",
    "            # ans.append(odd[i])\n",
    "            ans.extend([even[i], odd[i]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        result = []\n",
    "        for i in nums:\n",
    "            if i%2 == 0:\n",
    "                arr1.append(i)\n",
    "            else:\n",
    "                arr2.append(i)\n",
    "\n",
    "        for j in range(len(arr1)):\n",
    "            result.extend([arr1[j],arr2[j]])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst1=[]\n",
    "        lst2=[]\n",
    "        lst=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]%2==0:\n",
    "                lst1.append(nums[i])\n",
    "            else:\n",
    "                lst2.append(nums[i])\n",
    "        for t in range(len(lst1)):\n",
    "            lst.extend([lst1[t],lst2[t]])\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        a,b=0,1\n",
    "        for x in nums[::]:\n",
    "            if x%2==0:\n",
    "                ans.insert(a,x)\n",
    "                a+=2\n",
    "            else:\n",
    "                ans.insert(b,x)\n",
    "                b+=2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        for i in nums:\n",
    "            if not i&1:\n",
    "                arr1.append(i)\n",
    "            else:\n",
    "                arr2.append(i)\n",
    "        for j in range(len(arr1)):\n",
    "            result.extend([arr1[j],arr2[j]])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        l = len(nums)\n",
    "        m=[]\n",
    "        n=[]\n",
    "        s=[]\n",
    "        for i in range(l):\n",
    "            if nums[i]%2==0:\n",
    "                m.append(nums[i])\n",
    "            else:\n",
    "                n.append(nums[i])\n",
    "        for j in range(len(m)):\n",
    "            s+=[m[j],n[j]]\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        a=0\n",
    "        b=1\n",
    "        for x in nums[::]:\n",
    "            if x%2==0:\n",
    "                ans.insert(a,x)\n",
    "                a+=2\n",
    "            else:\n",
    "                ans.insert(b,x)\n",
    "                b+=2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]: \n",
    "        even = []\n",
    "        odd = []\n",
    "        for num in nums:\n",
    "            if num%2 == 0:\n",
    "                even.append(num)\n",
    "            else:\n",
    "                odd.append(num)\n",
    "        \n",
    "        res = []\n",
    "        for j in range(len(even)):\n",
    "            res.extend([even[j],odd[j]])\n",
    "# 为什么要用列表形式            \n",
    "        return res\n",
    "                \n",
    "            \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst1=[]\n",
    "        lst2=[]\n",
    "        lst3=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lst1.append(i)\n",
    "            else:lst2.append(i)\n",
    "        for pair in zip(lst1,lst2):\n",
    "            lst3.extend(pair)\n",
    "        return lst3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst1=[]\n",
    "        lst2=[]\n",
    "        lst3=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lst1.append(i)\n",
    "            else:lst2.append(i)\n",
    "        for pair in zip(lst1,lst2):\n",
    "            lst3.extend(pair)\n",
    "        return lst3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        jilist=[]\n",
    "        oulist=[]\n",
    "        newlist=[]\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]%2==0):\n",
    "                oulist.append(nums[i])\n",
    "            else:\n",
    "                jilist.append(nums[i])\n",
    "        #print(oulist,jilist)\n",
    "        for i in range(len(nums)):\n",
    "            if(i%2==0):\n",
    "                newlist.append(oulist[int(i/2)])\n",
    "            else:\n",
    "                newlist.append(jilist[int((i-1)/2)])\n",
    "        return newlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst=[]\n",
    "        lst1=[]\n",
    "        lst2=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lst2.append(i)\n",
    "            else:\n",
    "                lst1.append(i)\n",
    "        for j in range(len(lst1)):\n",
    "            lst.append(lst2[j])\n",
    "            lst.append(lst1[j])\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        ji = []\n",
    "        o =[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % 2 == 0:\n",
    "               o.append(nums[i])\n",
    "            else:\n",
    "                ji.append(nums[i])\n",
    "        d = []\n",
    "        i = 0\n",
    "        while len(d) != len(nums):\n",
    "            d.append(o[i])\n",
    "            d.append(ji[i])\n",
    "            i+=1\n",
    "        return d \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst1=[]\n",
    "        lst2=[]\n",
    "        lst3=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lst1.append(i)\n",
    "            else:lst2.append(i)\n",
    "        for pair in zip(lst1,lst2):\n",
    "            lst3.extend(pair)\n",
    "        return lst3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParityII(self, nums: List[int]) -> List[int]:\n",
    "        lst1=[]\n",
    "        lst2=[]\n",
    "        lst3=[]\n",
    "        for i in nums:\n",
    "            if i%2==0:\n",
    "                lst1.append(i)\n",
    "            else:lst2.append(i)\n",
    "        for pair in zip(lst1,lst2):\n",
    "            lst3.extend(pair)\n",
    "        return lst3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        result1 = []\n",
    "        result2 = []\n",
    "        for num in A:\n",
    "            if num%2:\n",
    "                result1.append(num)\n",
    "            else:\n",
    "                result2.append(num)\n",
    "        return result2+result1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: 'List[int]') -> 'List[int]':\n",
    "        if not A:\n",
    "            return\n",
    "        l = 0\n",
    "        r = len(A) - 1\n",
    "        while A[l] % 2 == 0 and l < r:\n",
    "            l += 1\n",
    "        while A[r] % 2 == 1 and r > l:\n",
    "            r -= 1\n",
    "        while l < r:\n",
    "            A[l], A[r] = A[r], A[l]\n",
    "            while A[l] % 2 == 0:\n",
    "                l += 1\n",
    "            while A[r] % 2 == 1:\n",
    "                r -= 1\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def odd_even_detected(self, num):\n",
    "        return (num & 1) == 0\n",
    "\n",
    "    def sortArrayByParity(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        length = len(A)\n",
    "        i = 0\n",
    "        a = []\n",
    "        b = []\n",
    "\n",
    "        # 数组里就一个数或者数组为空\n",
    "        if (1 == length) or (None == A):\n",
    "            return A\n",
    "\n",
    "        while i != length:\n",
    "            flag = self.odd_even_detected(A[i])\n",
    "            if True == flag:\n",
    "                a.append(A[i])\n",
    "            else:\n",
    "                b.append(A[i])\n",
    "            i += 1\n",
    "\n",
    "        a = a + b\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        head, tail = 0, len(A)-1\n",
    "        while head < tail:\n",
    "            left, right = A[head], A[tail]\n",
    "            if A[head]%2==1 and A[tail]%2==0:\n",
    "                A[head], A[tail] = right, left\n",
    "                head += 1\n",
    "                tail -= 1\n",
    "            elif A[head]%2 == 0:\n",
    "                head += 1\n",
    "            else:\n",
    "                tail -= 1\n",
    "            \n",
    "        return A\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dq=collections.deque()\n",
    "        for i in A:\n",
    "            if i%2==0:\n",
    "                dq.appendleft(i)\n",
    "            else:\n",
    "                dq.append(i)\n",
    "        return list(dq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        a=[]\n",
    "        b=[]\n",
    "        for i in A:\n",
    "            if i%2==0:\n",
    "                a.append(i)\n",
    "            else:\n",
    "                b.append(i)\n",
    "        return(a+b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(A)==0 or len(A)==1:\n",
    "            return A\n",
    "        left=0\n",
    "        right=1\n",
    "        while(right<len(A)):\n",
    "            while(left<len(A) and A[left]%2==0):\n",
    "                left+=1\n",
    "            print()\n",
    "            right=left+1\n",
    "            print(left,right)\n",
    "            while(right<len(A) and A[right]%2==1):\n",
    "                right+=1\n",
    "            \n",
    "            if left<len(A) and right<len(A):\n",
    "                temp=A[left]\n",
    "                A[left]=A[right]\n",
    "                A[right]=temp\n",
    "                left+=1\n",
    "            else:\n",
    "                break\n",
    "            # print(A)\n",
    "        return A\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        i, j = 0, len(A) - 1\n",
    "        while i < j:\n",
    "            if A[i] % 2 > A[j] % 2:\n",
    "                A[i], A[j] = A[j], A[i]\n",
    "                \n",
    "            if A[i] % 2 == 0: i+=1\n",
    "            if A[j] % 2 == 1: j-=1\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        even, odd,  result = [], [], []\n",
    "        for a in A:\n",
    "            if a%2 == 0:\n",
    "                even.append(a)\n",
    "            else:\n",
    "                odd.append(a)\n",
    "            \n",
    "            result = even + odd\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        k = len(A)-1\n",
    "        B = [0]*len(A)\n",
    "        for j in range(len(A)):\n",
    "            if A[j] % 2 == 0:\n",
    "                B[i] = A[j]\n",
    "                i += 1\n",
    "            else:\n",
    "                B[k] = A[j]\n",
    "                k -= 1\n",
    "                print(A[j],B[k])\n",
    "        return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: 'List[int]') -> 'List[int]':\n",
    "        even=[]\n",
    "        odd=[]\n",
    "        for each in A:\n",
    "            if each%2==1:\n",
    "                odd.append(each)\n",
    "            else:\n",
    "                even.append(each)\n",
    "        even.extend(odd)\n",
    "        return even\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        a = []\n",
    "        b = []\n",
    "        for i in A:\n",
    "            if i % 2 == 0:\n",
    "                a.append(i)\n",
    "            else:\n",
    "                b.append(i)\n",
    "        return a+b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        return ([x for x in A if x % 2 == 0] +\n",
    "                [x for x in A if x % 2 == 1])\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        odd, even = [], []\n",
    "        for num in A:\n",
    "            if num % 2 == 0:\n",
    "                even.append(num)\n",
    "            else:\n",
    "                odd.append(num)\n",
    "        even.extend(odd)\n",
    "        return even\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        l, r = 0, len(A) - 1\n",
    "        while l < r:\n",
    "            if A[l] & 1 and not A[r] & 1:\n",
    "                A[l], A[r] = A[r], A[l]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            elif not A[l] & 1:\n",
    "                l += 1\n",
    "            elif A[r] & 1:\n",
    "                r -= 1\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        left = 0\n",
    "        right = len(A) - 1\n",
    "        while(left < right):\n",
    "            if A[left]%2 == 0:\n",
    "                left += 1\n",
    "            elif A[right]%2 != 0:\n",
    "                right -= 1\n",
    "            else:\n",
    "                A[left], A[right] = A[right], A[left]\n",
    "        return A\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        evens,odds=[],[]\n",
    "        for i in A:\n",
    "            if i%2==0:\n",
    "                evens.append(i)\n",
    "            else:\n",
    "                odds.append(i)\n",
    "        for num in odds:\n",
    "            evens.append(num)\n",
    "        return evens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\r\n",
    "        if len(A) < 2:\r\n",
    "            return A\r\n",
    "        j = 0\r\n",
    "        for i in range(len(A)):\r\n",
    "            if A[i] % 2 == 0:\r\n",
    "                A[i], A[j] = A[j], A[i]\r\n",
    "                j += 1\r\n",
    "            i += 1\r\n",
    "        return A\r\n",
    "                \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        i,j = 0,1\n",
    "        res = [None] * len(A)\n",
    "        for num in A:\n",
    "            if num % 2 ==0:\n",
    "                res[i] = num\n",
    "                i += 1\n",
    "            else:\n",
    "                res[len(A)-j] = num\n",
    "                j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        return sorted(A, key=lambda x: x % 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, A: List[int]) -> List[int]:\n",
    "        res = ''\n",
    "        for i in A:\n",
    "            if i % 2:\n",
    "                res += f'{i}.'\n",
    "            else:\n",
    "                res = f'{i}.' + res\n",
    "        return res.split('.')[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        fast = 0\n",
    "        slow = 0\n",
    "        while fast < len(nums):\n",
    "            if nums[fast] % 2 == 0:\n",
    "                nums[fast], nums[slow] = nums[slow], nums[fast]\n",
    "                slow += 1\n",
    "            fast +=1\n",
    "        return (nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        return sorted(nums,key=lambda x:x % 2 != 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        i = 0\n",
    "        for j in range(len(nums)):\n",
    "            if nums[j] % 2 == 0:\n",
    "                nums[i],nums[j] = nums[j],nums[i]\n",
    "                i += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        p1 = 0\n",
    "        p2 = len(nums) - 1\n",
    "        newnums = [0] * len(nums)\n",
    "        for num in nums:\n",
    "            if num % 2:\n",
    "                newnums[p2] = num\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                newnums[p1] = num\n",
    "                p1 += 1\n",
    "        return newnums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        odds=[i for i in nums if i%2==1]\n",
    "        even=[i for i in nums if i%2==0]\n",
    "        return even+odds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "\n",
    "def cmp(x, y):\n",
    "    if (x % 2) == 0 and (y % 2) != 0:\n",
    "        return -1\n",
    "    elif (x % 2) != 0 and (y % 2) == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(key=cmp_to_key(cmp))\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        return reduce(lambda x, i: x + i if i[0] & 1 else i + x, list(map(lambda a: [a], nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        if not nums: return nums\n",
    "        \n",
    "        left, right = 0, len(nums) - 1\n",
    "        while (left <= right):\n",
    "            while (left <= right and nums[left] % 2 == 0): left += 1\n",
    "            while (left <= right and nums[right] % 2 == 1): right -= 1\n",
    "            if (left <= right):\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        j = -1\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[j] % 2 == 0):\n",
    "                nums.insert(0, nums[j])\n",
    "                nums.pop(j)\n",
    "            else:\n",
    "                j -= 1\n",
    "\n",
    "        return(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortArrayByParity(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            if i % 2 == 0 :\n",
    "                res.append(i)\n",
    "        for j in nums:\n",
    "            if j % 2 != 0 :\n",
    "                res.append(j)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
